package leetcode.hot100;


public class Solution394 {


    public static void main(String[] args) {

        String s = "3[a2[c]]";
        System.out.println(new Solution394().decodeString(s));
    }

    /**
        * @param s
        * @return java.lang.String
        * @desc decodeString
    */
    public String decodeString(String s) {
//        return decodeBracket1(s,-1,s.length());
        return decodeBracket(s,0)[0];
    }

    /**
        * @param s
    	* @param i
        * @return [右括号位置，解析的括号内容]
        * @desc 解析[i,...]
    */
    public String[] decodeBracket(String s, int i){
        StringBuilder sb = new StringBuilder();
        int multi = 0;
        while (i<s.length()){
            //遇到数字就加到repTime上，遇到左括号就重开递归，遇到右括号就返回，否则直接添到sb上
            if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                multi = multi*10+(s.charAt(i)-'0');
            }else if(s.charAt(i)=='['){
                String[] tmp = decodeBracket(s,i+1);
                i = Integer.parseInt(tmp[0]);
                while (multi-->0) sb.append(tmp[1]);
            }else if(s.charAt(i)==']'){
                return new String[]{String.valueOf(i),sb.toString()};
            }else {
                sb.append(s.charAt(i));
            }
            i++;
        }
        return new String[]{sb.toString()};
    }


    /**
        * @param s
    	* @param start 左括号位置
    	* @param end   右括号位置
        * @return java.lang.String  单独一对括号解码出的字符串
        * @desc 单独一对括号进行解码
    */
    public String decodeBracket1(String s, int start, int end){
        StringBuilder sb = new StringBuilder();
        //对于s[start,end]里的所有括号递归解析，将解析结果拼一起
        int cur = start+1;
        while (cur<end){
            char tmp = s.charAt(cur);
            if(tmp>='0'&&tmp<='9'){ //是一个数字,那就往后找，找到下一个左括号
                //获取内容重复次数
                int numStart = cur;
                while (s.charAt(cur)!='[') cur++;
                int repTime = Integer.valueOf(s.substring(numStart,cur));
                int leftBracket = cur;
                //找匹配的右括号
                int numLeftBracket = 1;
                while (numLeftBracket!=0){ //这里的遍历和后面的处理括号内容重复遍历了
                    cur++;
                    if(s.charAt(cur)=='[') numLeftBracket++;
                    if(s.charAt(cur)==']') numLeftBracket--;
                }
                int rightBracket = cur;
                //对该括号内的内容进行解码
                String subBrackt = decodeBracket1(s,leftBracket,rightBracket);
                //按重复次数添加解码内容
                for (int i = 0; i < repTime; i++) {
                    sb.append(subBrackt);
                }
            }else { //是一个字符
                sb.append(tmp);
            }
            cur++;
        }
        return sb.toString();
    }
}
